This invention relates to an authenticator of the type which is used to check that a message received at one end of a system has not been corrupted or changed during transmission of the message and also to verify the senders authority to transmit the message.
The authenticator may be applied to electronic transaction systems in which a user inserts a portable electronic token into a terminal which is connected to a central computer and in which messages concerning for instance the users bank account are transferred between the token and computer.
Typically, an authenticator is a one way algorithm A which can transform a message M to produce an authenticator code A(M). The authenticator code A(M) is generally small in size compared with the message M it was derived from and is analogous to a signature since it derives a code which is unique for each different message and cannot be forged without knowledge of the secret one-way function which was used to produce it. It is a one way algorithm since the message itself cannot be derived from the authenticator. When the message has been produced and an authenticator code calculated, the authenticator code is added to the message before it is sent to a receiver. The receiver thus receives both the message and the appended authenticator code. He passes the message through the same authenticator to produce his own authenticator code for the message. The two authenticator codes are then compared and if they are identical the receiver can be reasonably sure that the message received has not been altered since leaving the sender. An authenticator thus ensures firstly that a message has not been altered during transmission and secondly that the sender is verified to use the system since he possesses the same authenticator as the receiver.
An authenticator can be further modified by using a secret key system to select a particular way of implementing the authenticator algorithm. With the secret key K an authenticator is produced A(K,M) which is a function of both the authenticator and the secret key. Thus, even if the basic authenticator algorithm is known the secret keys can be witheld from public knowledge and the system remains secure. The keys can be varied at will, perhaps in a desired selected manner or maybe varied if one key has become compromised. Both sender and receiver must have the same secret key and authenticator for the receiver to be able to check the authenticator sent.
However, the number of different secret keys which can be used with an authenticator is limited by the size of the system and in an 8 byte key system a diligent cavesdropper could work through every possible secret key while attempting to break into the system. The present invention provides an improved system with a greater level of security.